package algorithmExample.Heap;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: zhangrongqing
 * @Date: 2019/11/13 10:04
 */
//编写一个程序，找出第 n 个丑数。
//
//        丑数就是只包含质因数 2, 3, 5 的正整数。
//
//        示例:
//
//        输入: n = 10
//        输出: 12
//        解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
//        说明:  
//
//        1 是丑数。
//        n 不超过1690。
public class UglyNumber {
    public List<Integer> uglyNumberList = new ArrayList<>(1690);

    public int nthUglyNumber(int n) {
        if (n == 1) {
            return 1;
        }
        //1是特殊的丑数
        uglyNumberList.add(1);
        int num = 2;
        while (uglyNumberList.size() <= 1690) {
            if (isUgly(num)) {
//                System.out.printf("number:%s is an ugle number",num);
                uglyNumberList.add(num);
                if (uglyNumberList.size() == n) {
                    return uglyNumberList.get(n - 1);
                }
            }
            num++;
        }
        return 0;
    }

    private boolean isUgly(int number) {
        if (number % 2 == 0 && uglyNumberList.contains(number / 2)) {
            return true;
        }
        if (number % 3 == 0 && uglyNumberList.contains(number / 3)) {
            return true;
        }
        if (number % 5 == 0 && uglyNumberList.contains(number / 5)) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        int result = new UglyNumber().nthUglyNumber(342);
        System.out.printf("calc result is %s", result);

        Boolean aBlooean = new UglyNumber().isUgly(7);
    }
}
